The rapidly growing Internet is convenient, but there are concerns about its security on the other hand, so that there are increasing needs for cryptographic technology to ensure the secrecy of communication. Cryptographic systems that are currently used in general can be divided into secret key cryptography, such as DES (Data Encryption Standard) and Triple DES, and public key cryptography, such as RSA (Rivest Shamir Adleman) and elliptic curve cryptography. However, these are cipher communication methods that ensure the security based on the “complexity of computation” and are in constant jeopardy of being cracked by an enormous volume of computation or at the advent of a cryptanalytic algorithm. In such a background, the quantum key distribution system (QKD) has attracted attention as a technology for cryptographic key distribution that “will never be eavesdropped.”
In QKD, photons are generally used for communication media, and information is transmitted by being encoded in the quantum states of photons, such as their polarization, phase, and the like. An eavesdropper on a transmission link eavesdrops on information by tapping the photons that are being transmitted or by any other way. However, according to Heisenberg uncertainty principle, it is impossible to perfectly return photons once observed to their quantum states before they were observed, and so a change occurs in the statistical values of received data detected by a legitimate receiver. The receiver can detect the eavesdropper on the transmission link by detecting such a change.
In a case of quantum key distribution utilizing photon polarization, a sending-side communication device and a receiving-side communication device (hereinafter, referred to as “Alice” and “Bob,” respectively) organize an optical interferometer, and Alice and Bob individually modulate the phase of each photon at random. The difference in depth between these modulated phases provides an output of 0 or 1. Thereafter, Alice and Bob reconcile part of the conditions used when the output data were measured, whereby the same string of bits can be finally shared between Alice and Bob. Hereinafter, a flow of general quantum cryptographic key creation will be described briefly, with reference to FIG. 1.
Referring to FIG. 1, random numbers generated at Alice are transmitted to Bob through quantum key distribution (single photon transmission), but a large volume of information is lost along a transmission link. A string of random numbers shared at this stage between Alice and Bob is called a raw key (raw-key sharing S1). Subsequently, Alice and Bob perform basis reconciliation, thereby discarding bits whose bases do not match (sequence S1.5). An obtained string of shared random numbers, whose volume is half the original volume due to this process, is called a sifted key (sifted-key sharing S2).
Then, after undergoing an error correction process to correct errors that have crept in at the stage of quantum key distribution, a remaining error detection process to detect remaining errors that cannot be corrected by the error correction, and privacy amplification to screen out a volume of information that is supposed to be leaked to an eavesdropper (sequence S2.5), the remaining ones become a final key that will be actually used as a cryptographic key (final-key sharing S3). The final key thus created is not only used as a cryptographic key for encrypted communication but also used for message authentication to check whether a communication that a transmitter and a receiver have performed is not tampered.
Here, if an error is included in key information to be put into privacy amplification processing, the error is amplified in the privacy amplification processing. As disclosed in NPT 1, the error rate becomes m/2 times the original rate when privacy amplification processing is performed by using a general Toeplitz matrix with a size of m×n, and becomes (n−m)m/2n times the original rate when a privacy amplification method as disclosed in PTL 1 is used. As disclosed in NPT 2, it is preferable that n bits for the matrix size used in privacy amplification processing are not less than 100 kbits, considering the effect of statistical fluctuations occurring when an estimation of the volume of leaked information is made. Therefore, in any one of the above-described privacy amplification methods, the error rate after privacy amplification processing becomes several tens of thousands times higher than the error rate before the processing. Accordingly, it is necessary to make the error rate of key information sufficiently small through error correction and remaining error detection processing when the key information is put into privacy amplification processing.
<Error Correction and Remaining Error Detection Processing>
For the error correction processing, for example, a method as shown in NPL 3 is used. In this method, key information is divided into a plurality of blocks at Alice and Bob, and the parity of each block is checked, whereby a block including an error is identified. Then, error correction is performed by applying a Hamming code or the like to such a block. In addition, supposing that a single block might include an even number of errors, a string of secret bits is rearranged, and then parity check and error correction are performed again.
FIG. 2 shows an example of the remaining error detection processing when the number of parity calculations V=4. In the remaining error detection processing, about half of the bits of key information are chosen out at random, and the parity thereof is checked between Alice and Bob. When parities do not match, the above-described error correction processing is performed again. As shown in FIG. 2, the error rate of a shared key becomes 1/24 or lower after parity check is repeated four times. However, since information about a cryptographic key is leaked through parity check, it is necessary to discard as many bits as the number of times (V) parity check is performed. In the example shown in FIG. 2, since parity check is repeated V=4 times for key information of 24 bits, 4 bits are discarded, with key information of 20 bits remaining. Accordingly, if the number of parity checks is increased in order to ensure a lower error rate, discarded bits increase, resulted in the rate of creation of a final key being degraded.
<Final Key>
Referring back to FIG. 1, the cryptographic key shared through QKD as described above is used for various purposes. One of the most typical uses is to encrypt and decrypt a common encrypted communication (encrypted communication S4). For such a use, there is a method of use in which a cryptographic key is used once and discarded in a one-time-pad manner, and there is another method of use to periodically update an AES (Advanced Encryption Standard) cryptographic key.
Moreover, the security of a cryptographic key cannot be ensured if the contents of communications (S1.5 and S2.5) performed between Alice and Bob in the process of sharing a cryptographic key in QKD are tampered. Accordingly, message authentication needs to be performed, and the cryptographic key is also used for this message authentication (message authentication S5).
An authentication method disclosed in NPL 4 is a method that can ensure information-theoretic security. FIG. 3 shows an example of a use thereof. Referring to FIG. 3, a message is sequentially shortened by matrix operation or the like using a cryptographic key, and a hash value is calculated. When the hash values calculated by Alice and Bob are different from each other, it is determined that there is a possibility that the content of a communication has been tampered, and a cryptographic key corresponding to the content of the communication for which this hash value is calculated is discarded.